#include <iostream>
#include "trace.h"
#include "general.h"
#include "constants.h"
#include <deque>
#include <vector>
#include <ctime>
#include <string>

using namespace std;

struct ACKcon_node
{
	Position pos;
	int globalID;
	int domainID;
	
	int totalBuffer;
	int totalSend;
	int totalReceive;
	deque<Traffic> nodeTraffic;

	bool isSender;
	int sendTo;
	int receiveFrom;

	int state;
	int countingDown;
	int backoff;

	int contendSubcarrier;
	int ackSubcarrier;
};

struct ACKcon
{
/*
	SIFS-SFC-DATA-(SIFS-RFC-DATA)-ACK
*/
	ACKcon_node ackcon_nodes[2][MAX_NODE];		// keep two copys
	vector<int> ackcon_neighborList[MAX_NODE];	// keep the neighbors
	Trace trace;
	int nodeNum;
	ofstream msgout;
	int t_data;				// time needed for data transmission
	//int datarate;			// in (Mbps)

	int receiveCount;
	int sendCount;
	int collisionCount;
	int time;

	void initial(Trace trace, int datarate = 6)
	{
		this->trace = trace;
		this->nodeNum = trace.nodeNum;
		memset(ackcon_nodes, 0, sizeof(ACKcon_node));

		this->t_data = 1500 * 8 / datarate;

		// initial nodes' location, id, etc.
		for (int i = 0; i < trace.nodeNum; i++)
		{
			for (int j = 0; j < 2; j++)
			{
				ackcon_nodes[j][i].globalID = i;
				ackcon_nodes[j][i].domainID = trace.nodes_id[i];
				ackcon_nodes[j][i].pos = trace.nodes_position[i];
				ackcon_nodes[j][i].isSender = false;
				ackcon_nodes[j][i].totalBuffer = 0;
				ackcon_nodes[j][i].totalReceive = 0;
				ackcon_nodes[j][i].totalSend = 0;
				ackcon_nodes[j][i].backoff = 0;
				ackcon_nodes[j][i].nodeTraffic.clear();
				ackcon_nodes[j][i].state = STATE_IDLE;
				ackcon_nodes[j][i].contendSubcarrier = 0;
				ackcon_nodes[j][i].ackSubcarrier = -1;
				ackcon_nodes[j][i].countingDown = 0;
			}
		}

		msgout.open("ackcon_debug.txt");
		// initial nodes' neighbors
		for (int i = 0; i < nodeNum; i++)
		{
			cout << i << " : ";
			msgout << i << " : ";
			for (int j = 0; j < nodeNum; j++)
			{
				if (i != j && ackcon_nodes[0][i].pos.isNeighbor(ackcon_nodes[0][j].pos))
				{
					ackcon_neighborList[i].push_back(j);
					cout << j << ", ";
					msgout << j << ", ";
				}
			}
			cout << endl;
			msgout << endl;
		}
	}

	// run the ackcon_mac, for runtime (in millisecond)
	void start_mac(int runtime = 0)
	{
		int seed = (unsigned int)std::time(NULL);
		srand(seed);
		msgout << seed << endl;

		time = 0;
		this->receiveCount = 0;
		this->sendCount = 0;
		this->collisionCount = 0;

		while (time < runtime * 1000 || runtime == 0)		// runtime == 0: wait until all over
		{
			time++;

			// check traffic trace for all the nodes
			if (!trace.nodes_traffic.empty())
			{
				while (trace.nodes_traffic[0].time_slot <= time)
				{
					int sender = trace.nodes_traffic[0].sender_id;
					int pkt = trace.nodes_traffic[0].pkt_number;
					for (int i = 0; i < 2; i++)
					{
						ackcon_nodes[i][sender].totalBuffer += pkt;
						ackcon_nodes[i][sender].nodeTraffic.push_back(trace.nodes_traffic[0]);
					}
					trace.nodes_traffic.pop_front();
					if (trace.nodes_traffic.empty())
						break;
				}
			}
			else	// actually no work to do
			{
				int shouldExit = true;
				for (int id = 0; id < nodeNum; id++)
					if (ackcon_nodes[0][id].totalBuffer != 0)
					{
						shouldExit = false;
						break;
					}
				if (shouldExit)
					break;
			}

			for (int id = 0; id < nodeNum; id++)
			{
				switch (this->ackcon_nodes[0][id].state)
				{
				case STATE_IDLE:
					process_idle(id, time);
					break;
				case STATE_SIFS1:
					process_sifs1(id, time);
					break;
				case STATE_SIFS2:
					process_sifs2(id, time);
					break;
				case STATE_SIFS3:
					process_sifs3(id, time);
					break;
				case STATE_SFC	:
					process_sfc(id, time);
					break;
				case STATE_NAV	:
					process_nav(id, time);
					break;
				case STATE_SDATA:
					process_sdata(id, time);
					break;
				case STATE_RDATA:
					process_rdata(id, time);
					break;
				case STATE_SACK :
					process_sack(id, time);
					break;
				case STATE_RACK:
					process_rack(id, time);
					break;
				}
			}
			copyState();							// copy the state of [1] to [0];
		}

		for (int i = 0; i < nodeNum; i++)
		{
			receiveCount += this->ackcon_nodes[0][i].totalReceive;
			sendCount += this->ackcon_nodes[0][i].totalSend;
		}
		
		msgout << receiveCount << " " << sendCount << " " << collisionCount << endl;
		cout << receiveCount << " " << sendCount << " " << collisionCount << endl;

		msgout.close();
	}

	void copyNode(const ACKcon_node& from, ACKcon_node &to)
	{
		//Position pos;
		//int globalID;
		//int domainID;
	
		to.totalBuffer = from.totalBuffer;
		to.totalSend = from.totalSend;
		to.totalReceive = from.totalReceive;
		to.backoff = from.backoff;

		to.nodeTraffic.clear();
		for (deque<Traffic>::const_iterator it = from.nodeTraffic.begin(); it != from.nodeTraffic.end(); it++)
		{
			to.nodeTraffic.push_back(*it);
		}

		to.isSender = from.isSender;
		to.sendTo = from.sendTo;
		to.receiveFrom = from.receiveFrom;;

		to.state = from.state;
		to.countingDown = from.countingDown;

		to.contendSubcarrier = from.contendSubcarrier;
		to.ackSubcarrier = from.ackSubcarrier;
	}

	void copyState()
	{
		for (int i = 0; i < nodeNum; i++)		
		{
			copyNode(ackcon_nodes[1][i], ackcon_nodes[0][i]);
		}
	}

	void process_rack(int id, int time)
	{
		ACKcon_node &node_old = ackcon_nodes[0][id];
		ACKcon_node &node_new = ackcon_nodes[1][id];

		if (node_new.countingDown > 0)
		{
			node_new.countingDown--;
		}
		else
		{
			if (this->ackcon_nodes[0][node_new.receiveFrom].nodeTraffic[0].pkt_number == 1)	// whether anything more
			{
				updateStateMsg(time, node_new, "RACK-->NAV");
				node_new.state = STATE_NAV;
				node_new.countingDown = this->t_data - 1;
				node_new.isSender = false;
				node_new.sendTo = -1;
				node_new.receiveFrom = -1;
				node_new.ackSubcarrier = -1;
				node_new.contendSubcarrier = -1;
			}
			else
			{
				if (checkConWin(node_new.receiveFrom))	// whether wins
				{
					// win, be a sender and move to sdata
					updateStateMsg(time, node_new, "RACK-->RDATA");
					node_new.state = STATE_RDATA;
					node_new.countingDown = this->ackcon_nodes[0][node_old.receiveFrom].countingDown - 1;
					node_new.isSender = false;
					node_new.sendTo = -1;
					node_new.receiveFrom = node_old.receiveFrom;	// the same sender
					node_new.ackSubcarrier = -1;
					node_new.contendSubcarrier = -1;
					return;							
				}
				else									// lose, go to idle
				{
					updateStateMsg(time, node_new, "RACK-->NAV");
					node_new.state = STATE_NAV;
					node_new.countingDown = this->t_data - 1;
					node_new.isSender = false;
					node_new.sendTo = -1;
					node_new.receiveFrom = -1;
					node_new.ackSubcarrier = -1;
					node_new.contendSubcarrier = -1;
					return;							
				}
			}
		}
	}

	void process_sifs3(int id, int time)
	{
		ACKcon_node &node_old = ackcon_nodes[0][id];
		ACKcon_node &node_new = ackcon_nodes[1][id];

		if (node_new.countingDown > 0)
		{
			node_new.countingDown--;
		}
		else
		{
			updateStateMsg(time, node_new, "SIFS3-->RACK");
			node_new.state = STATE_RACK;
			node_new.countingDown = T_FCON;
			node_new.contendSubcarrier = rand() % NUM_CONT_SUBCARRIER + 1;
			node_new.ackSubcarrier = node_new.receiveFrom;		// mark ack
			return;
		}
	}

	void process_rdata(int id, int time)
	{
		ACKcon_node &node_old = ackcon_nodes[0][id];
		ACKcon_node &node_new = ackcon_nodes[1][id];

		if (node_new.countingDown > 0)
		{
			if (checkCollision(id, node_new.receiveFrom))	// collision, back to idle
			{
				updateStateMsg(time, node_new, "RDATA-->IDLE");
				node_new.state = STATE_IDLE;
				node_new.isSender = false;
				node_new.receiveFrom = -1;
				node_new.sendTo = -1;
				node_new.countingDown = 0;
				node_new.ackSubcarrier = -1;
				node_new.contendSubcarrier = -1;
				return;				
			}
			else
				node_new.countingDown--;
		}
		else
		{
			node_new.totalReceive++;		// received one more packet
			updateStateMsg(time, node_new, "RDATA-->SIFS3");
			node_new.state = STATE_SIFS3;
			node_new.countingDown = T_SIFS;
			node_new.contendSubcarrier = -1;
			return;			
		}
	}

	void process_nav(int id, int time)
	{
		ACKcon_node &node_old = ackcon_nodes[0][id];
		ACKcon_node &node_new = ackcon_nodes[1][id];

		if (node_new.countingDown > 0)
		{
			int senderID = -1;
			if (checkReceiver(node_new.globalID, senderID))		// someone in SDATA, and the receiver is this node
			{
				updateStateMsg(time, node_new, "NAV-->RDATA");
				node_new.state = STATE_RDATA;
				node_new.receiveFrom = senderID;
				node_new.isSender = false;
				node_new.sendTo = -1;
				node_new.countingDown = this->ackcon_nodes[0][senderID].countingDown - 1;
				return;
			}
			else
				node_new.countingDown--;
		}
		else
		{
			updateStateMsg(time, node_new, "NAV-->IDLE");
			node_new.state = STATE_IDLE;
			node_new.countingDown = 0;
			node_new.isSender = false;
			node_new.sendTo = -1;
			node_new.receiveFrom = -1;
			node_new.ackSubcarrier = -1;
			node_new.contendSubcarrier = -1;
			return;	
		}
	}

	void process_sack(int id, int time)
	{
		ACKcon_node &node_old = ackcon_nodes[0][id];
		ACKcon_node &node_new = ackcon_nodes[1][id];

		if (node_new.countingDown > 0)
		{
			node_new.countingDown--;
		}
		else
		{
			if (!checkDataCollision(id, node_new.sendTo) 
				&& this->ackcon_nodes[0][node_new.sendTo].ackSubcarrier == id
				)	// whether ack it's possible that ack collision by other data
			{
				node_new.totalSend++;
				node_new.nodeTraffic[0].pkt_number--;
				node_new.totalBuffer--;
				node_new.backoff = 0;
				finishPktMsg(time, node_new.globalID, node_new.sendTo);
				if (node_new.nodeTraffic[0].pkt_number == 0)	// whether anything more
				{
					node_new.nodeTraffic.pop_front();
					updateStateMsg(time, node_new, "SACK-->NAV");
					node_new.state = STATE_NAV;
					node_new.countingDown = this->t_data - 1;
					node_new.isSender = false;
					node_new.sendTo = -1;
					node_new.receiveFrom = -1;
					node_new.ackSubcarrier = -1;
					node_new.contendSubcarrier = -1;
				}
				else
				{
					if (checkConWin(node_new.sendTo))	// whether wins
					{
						// win, be a sender and move to sdata
						updateStateMsg(time, node_new, "SACK-->SDATA");
						node_new.state = STATE_SDATA;
						node_new.countingDown = this->t_data;
						node_new.isSender = true;
						node_new.sendTo = node_new.nodeTraffic[0].receiver_id;
						node_new.receiveFrom = -1;
						node_new.ackSubcarrier = -1;
						node_new.contendSubcarrier = -1;
						return;							
					}
					else									// lose, go to nav, need stay silence for a peroid
					{
						updateStateMsg(time, node_new, "SACK-->NAV");
						node_new.state = STATE_NAV;
						node_new.countingDown = this->t_data - 1;
						node_new.isSender = false;
						node_new.sendTo = -1;
						node_new.receiveFrom = -1;
						node_new.ackSubcarrier = -1;
						node_new.contendSubcarrier = -1;
						return;							
					}
				}
			}
			else	// no ack, need retransmission
			{
				this->collisionCount++;
				if (node_new.backoff < 3)
					node_new.backoff++;

				collisionMessage(time, node_new);
				updateStateMsg(time, node_new, "SACK-->NAV");
				node_new.state = STATE_NAV;
				node_new.countingDown = this->t_data;
				// IMPORTANT, time domain backoff is still needed
				int backoff = rand() % node_new.backoff;
				for (int i = 0; i < backoff; i++)
				{
					// the backoff time should be designed carefully
					// in every stage, the countingDown will countdown until 0, so we have to + 1
					node_new.countingDown += T_SIFS + 1 + T_FCON + 1 + this->t_data + 1;
				}
				node_new.countingDown  -= 1;
				node_new.isSender = false;
				node_new.sendTo = -1;
				node_new.receiveFrom = -1;
				node_new.ackSubcarrier = -1;
				node_new.contendSubcarrier = -1;
				return;
			}
		}
	}

	void process_sifs2(int id, int time)
	{
		ACKcon_node &node_old = ackcon_nodes[0][id];
		ACKcon_node &node_new = ackcon_nodes[1][id];

		if (node_new.countingDown > 0)
		{
			node_new.countingDown--;
		}
		else
		{
			updateStateMsg(time, node_new, "SIFS2-->SACK");
			node_new.state = STATE_SACK;
			node_new.countingDown = T_FCON;
			node_new.ackSubcarrier = -1;
			node_new.contendSubcarrier = -1;
			return;
		}
	}	

	void process_sdata(int id, int time)
	{
		ACKcon_node &node_old = ackcon_nodes[0][id];
		ACKcon_node &node_new = ackcon_nodes[1][id];

		if (node_new.countingDown > 0)
		{
			node_new.countingDown--;
		}
		else
		{
			updateStateMsg(time, node_new, "SDATA-->SIFS2");
			node_new.state = STATE_SIFS2;
			node_new.countingDown = T_SIFS;
			node_new.ackSubcarrier = -1;
			node_new.contendSubcarrier = -1;
			return;				
		}
	}	

	void process_sfc(int id, int time)
	{
		ACKcon_node &node_old = ackcon_nodes[0][id];
		ACKcon_node &node_new = ackcon_nodes[1][id];

		if (node_new.countingDown > 0)
		{
			node_new.countingDown--;
		}
		else	// end of sfc, check if it wins
		{
			if (checkConWin(id))
			{
				// win, be a sender and move to sdata
				updateStateMsg(time, node_new, "SFC-->SDATA");
				node_new.state = STATE_SDATA;
				node_new.countingDown = this->t_data;
				node_new.isSender = true;
				node_new.sendTo = node_new.nodeTraffic[0].receiver_id;
				node_new.receiveFrom = -1;
				node_new.ackSubcarrier = -1;
				node_new.contendSubcarrier = -1;
				return;	
			}
			else	// lose, go back to SIFS1
			{
				updateStateMsg(time, node_new, "SFC-->NAV");
				node_new.state = STATE_NAV;
				node_new.countingDown = this->t_data - 1;
				node_new.isSender = false;
				node_new.sendTo = -1;
				node_new.receiveFrom = -1;
				node_new.ackSubcarrier = -1;
				node_new.contendSubcarrier = -1;
				return;	
			}
		}
	}

	void process_sifs1(int id, int time)
	{
		ACKcon_node &node_old = ackcon_nodes[0][id];
		ACKcon_node &node_new = ackcon_nodes[1][id];

		if (node_new.countingDown > 0)
		{
			if (checkCollision(id, id))
			{
				int senderID = -1;
				if (checkReceiver(node_new.globalID, senderID))		// someone in SDATA, and the receiver is this node
				{
					updateStateMsg(time, node_new, "SIFS1-->RDATA");
					node_new.state = STATE_RDATA;
					node_new.receiveFrom = senderID;
					node_new.isSender = false;
					node_new.sendTo = -1;
					node_new.countingDown = this->ackcon_nodes[0][senderID].countingDown - 1;
					return;
				}
				else
					node_new.countingDown = T_SIFS;
			}
			else
				node_new.countingDown--;
		}
		else // end of SIFS1, go to SFC
		{
			// the case for the first packet, the sender should contend for itself
			updateStateMsg(time, node_new, "SIFS1-->SFC");
			node_new.state = STATE_SFC;
			node_new.contendSubcarrier = rand() % NUM_CONT_SUBCARRIER + 1;
			node_new.countingDown = T_SFC;
			return;			
		}
	}

	void process_idle(int id, int time)
	{
		ACKcon_node &node_old = ackcon_nodes[0][id];
		ACKcon_node &node_new = ackcon_nodes[1][id];
		if (node_old.totalBuffer != 0)
		{
			updateStateMsg(time, node_new, "IDLE-->SIFS1");
			node_new.state = STATE_SIFS1;
			node_new.countingDown = T_SIFS;
			node_new.contendSubcarrier = 0;
			node_new.ackSubcarrier = -1;
		}
		else 
		{
			int senderID = -1;
			if (checkReceiver(node_new.globalID, senderID))		// someone in SDATA, and the receiver is this node
			{
				updateStateMsg(time, node_new, "IDLE-->RDATA");
				node_new.state = STATE_RDATA;
				node_new.receiveFrom = senderID;
				node_new.isSender = false;
				node_new.sendTo = -1;
				node_new.countingDown = this->ackcon_nodes[0][senderID].countingDown - 1;
			}
		}
	}

	// whether the node wins in the contension
	bool checkConWin(int nodeID)
	{
		ACKcon_node node = this->ackcon_nodes[0][nodeID];
		int winSubcarrier = node.contendSubcarrier;
		if (winSubcarrier <= 0)
			return false;

		// find the smallest subcarrier from the neighbors
		for (vector<int>::iterator it = this->ackcon_neighborList[nodeID].begin(); it != this->ackcon_neighborList[nodeID].end(); it++)
		{
			ACKcon_node neighbor = ackcon_nodes[0][*it];

			if (neighbor.contendSubcarrier < winSubcarrier && neighbor.contendSubcarrier > 0)
			{
				return false;
			}
		}

		return true;
	}

	// whether some neighbor wants to send someting to node and this node win in the contension
	bool checkReceiver(int receiverID, int& senderID)
	{
		ACKcon_node receiver = this->ackcon_nodes[0][receiverID];
		senderID = -1;
		for (vector<int>::iterator it = this->ackcon_neighborList[receiverID].begin(); it != this->ackcon_neighborList[receiverID].end(); it++)
		{
			ACKcon_node neighbor = ackcon_nodes[0][*it];

			// some neighbor has perform contension
			if (neighbor.isSender && neighbor.state == STATE_SDATA && neighbor.sendTo == receiverID && neighbor.countingDown >= this->t_data - 10)
			{
				senderID = neighbor.globalID;
			}
		}

		// no one is in SFC
		if (senderID < 0)
			return false;
		else if (checkCollision(receiverID, senderID))
			return false;
		else
			return true;
	}

	// whether the link sender-->receiver is failed due to collision
	bool checkCollision(int receiverID, int senderID)
	{
		ACKcon_node receiver = this->ackcon_nodes[0][receiverID];
		ACKcon_node sender = this->ackcon_nodes[0][senderID];
		for (vector<int>::iterator it = this->ackcon_neighborList[receiverID].begin(); it != this->ackcon_neighborList[receiverID].end(); it++)
		{
			ACKcon_node neighbor = ackcon_nodes[0][*it];
			if (neighbor.globalID == sender.globalID)
				continue;

			// someone else is also a sender
			if (neighbor.state == STATE_SDATA || neighbor.state == STATE_SFC || neighbor.state == STATE_RACK)
			{
				return true;
			}
		}
		return false;
	}

	bool checkDataCollision(int receiverID, int senderID)
	{
		ACKcon_node receiver = this->ackcon_nodes[0][receiverID];
		ACKcon_node sender = this->ackcon_nodes[0][senderID];
		for (vector<int>::iterator it = this->ackcon_neighborList[receiverID].begin(); it != this->ackcon_neighborList[receiverID].end(); it++)
		{
			ACKcon_node neighbor = ackcon_nodes[0][*it];
			if (neighbor.globalID == sender.globalID)
				continue;

			// someone else is sending data
			if (neighbor.state == STATE_SDATA)
			{
				return true;
			}
		}
		return false;
	}

	void collisionMessage(int time, const ACKcon_node& node)
	{
		cout << time << " COLLISION: " << node.globalID << "-->" << node.sendTo << endl;
		msgout << time << " COLLISION: " << node.globalID << "-->" << node.sendTo << endl;
	}

	void updateStateMsg(int time, const ACKcon_node& node, string msg)
	{
		// Use this to print something
		//string not = "";
		//if (!node.isSender)
		//	not += " NOT";
		//cout << time << " node " << node.globalID << "(" << node.domainID << ") is" << not << " sender: " << msg << endl;
		//msgout << time << " node " << node.globalID << "(" << node.domainID << ") is" << not << " sender: " << msg << endl;
	}

	void finishPktMsg(int time, int from, int to)
	{
		cout << time << " FINISH: " << from << "-->" << to << endl;
		msgout << time << " FINISH: " << from << "-->" << to << endl;
	}
};